/**
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 *
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 * 思路：回溯
 * https://leetcode.cn/problems/subsets/
 */
class Subsets {
    List<List<Integer>> ret=new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        Deque<Integer> qu=new LinkedList<>();
        dfs(nums,qu,0,nums.length);
        return ret;
    }
    public void dfs(int[]nums,Deque<Integer> qu,int begin,int len){
        if(begin>len){
            return;
        }
        ret.add(new ArrayList<>(qu));
        for(int i=begin;i<len;i++){
            qu.offerLast(nums[i]);
            dfs(nums,qu,i+1,len);
            qu.pollLast();
        }
    }
    
}